# 优化后的求质数方法
def listPrimes2(n: int):
    primes = []
    nums = [True] * (n + 1)
    for x in range(2, n + 1):
        if nums[x]:
            primes.append(x) # x 为质数
            for y in range(x + x, n + 1, x):
                nums[y] = False # x的倍数均为合数
    print(*primes)

# main
n = int(input('请输入n，让我计算n以内的所有质数：'))
listPrimes2(n)
